1. Field of Invention
The present invention relates generally to methods and apparatus for transmitting digital data in a packet-switched computer network. More specifically, the present invention relates to a packet prioritization processing technique for routing traffic in a packet-switched computer network.
2. Routers and Network Protocol
A computer network is a geographically distributed collection of interconnected communication links for transporting data between nodes, such as computers. By definition, a network is a group of computers and associated devices that are connected by communications facilities or links. Network connections can be of a permanent nature, such as via cables, or can be of a temporary nature, such as connections made through telephone or other communication links. A plurality of computer networks may be further interconnected by intermediate nodes, or routers, to extend the effective xe2x80x9csizexe2x80x9d of the networks, smaller portions of which may be maintained as autonomous domains of nodes. A router is computer system that stores and forwards data packets from one local area network (LAN) or wide area network (WAN) to another. Routers see the network as network addresses and all the possible 10 paths between them. They read the network address in a transmitted message and can make a decision on how to send it based on the most expedient route (traffic load, line costs, speed, bad lines, etc.). Routers typically communicate by exchanging discrete xe2x80x9cpacketsxe2x80x9d of data according to predefined protocols. In this context, a protocol comprises a set of rules defining how the nodes interact with each other.
Networks vary in size, from a local area network (LAN) consisting of a few computers and related devices, to a wide area network (WAN) which interconnects computers and LANS that are geographically dispersed. An internetwork, in turn, is the joining of multiple computer networks, both similar and dissimilar, by means of gateways or routers that facilitate data transfer and conversion from various networks. A well known abbreviation for internetwork is internet. As currently understood, the capitalized term Internet refers to the collection of networks and gateways that uses a Transmission Control Protocol/Internet Protocol (TCP/IP). The Internet has recently seen explosive growth by virtue of its ability to link computers located throughout the world.
FIG. 1 shows a diagram of an IP network, which is an example of one type of flow-based network in which the technique of the present invention may be implemented. A flow can be a hard-state virtual circuit in an ATM network, a soft-state flow in an IP network (e.g., a MPLS tunnel), or a stateless connection as a TCP/IP connection in today""s Internet. As shown in FIG. 1, the IP network 2 includes the Internet (or a WAN) 4 over which a Node 16 (e.g. a computer) can communicate with a separate node 6 via a plurality of intermediate nodes (e.g. R1, R3, R4). Node 6 may be, for example, a server which is part of Local Area Network (LAN) 7, connected to the Internet via routers R1 and R3. Router R3 (10) may, in turn, connect one or more other routers (e.g., router R2) with the Internet.
A LAN is a communication network that serves users within a confined geographical area. It is made up of servers, workstations, a network operating system and a communications link. Servers are high-speed machines that hold programs and data shared by all network users. The workstations, or clients, are the user"" personal computers, which perform stand-alone processing and access the network servers as required The controlling software in a LAN is the network operating system, such as, for example, NetWare, UNIX, and/or Appletalk, which resides in the server. Message transfer is managed by a transport protocol such as, for example, IPX, SPX, SNA and/or TCP/IP. The physical transmission of data is performed by the access method (Ethernet, Token Ring, etc.) which is implemented in the network adapters that plug into the machines. The actual communications path is the cable (twisted pair, coax, optical fiber) that interconnects each network adapter.
In order to reduce design complexity, most networks are organized as a series of hardware and software levels or xe2x80x9clayersxe2x80x9d within each node. These layers interact to format data for transfer between, e.g., a source node and a destination node communicating over the network. Specifically, predetermined services are performed on the data as it passes through each layer and the layers communicate with each other by means of the predefined protocols. This layered design permits each layer to offer selected services to other layers using a standardized interface that shields those layers from the details of actual implementation of the services. The layered protocols, commonly referred to as protocol stacks, are described in greater detail with reference to FIG. 2.
FIG. 2 illustrates the relationship of subnetworks and gateways to layered protocols. Assume that the user application 202A in host A sends an application protocol data unit (PDU) to an application layer protocol 202B in host B, such as, for example, a file transfer system. The file transfer software performs a variety of functions and sends file records to the user data. In many systems, the operations at host B are known as server operations and the operations at host A are know as client operations.
As indicated by the downward arrows in the protocol stack at host A, this unit is passed to the transport layer protocol 204A, which performs a variety of operations and adds a header to the PDU passed to it. At this point, the unit of data is often referred to as a segment. The PDU from the upper layers is considered to be data to the transport layer.
Next, the transport layer passes the segment to the network layer 206A, also called the IP layer, which again performs specific services and appends a header. This unit (now called a datagram in internet terms) is passed down to the lower layers. Here, the data link layer adds its header as well as a trailer, and the data unit (now called a frame) is launched into subnetwork 210 by the physical layer 208A. Of course, if host B sends data to host A, the process is reversed and the direction of the arrows is changed.
Internet protocols are typically unaware of what goes on inside the network. The network manager is free to manipulate and manage the PDU in any manner necessary. In some instances, however, the internet PDU (data and headers) remains unchanged as it is transmitted through the subnet. In FIG. 2, it emerges at the gateway where it is processed through the lower layers 214 and passed to the IP (network) layer 212. Here, routing decisions are made based on the destination address provided by the host computer.
After these routing decisions have been made, the PDU is passed to the communications link connected to the appropriate subnetwork (comprising the lower layers). The PDU is re-encapsulated into the data link layer frame and passed to the next subnetwork 216, where it finally arrives at the destination host.
The destination (host B) receives the traffic through its lower layers and reverses the process that transpired at host A; it de-encapsulates the headers by stripping them off in the appropriate layer. The header is used by the layer to determine the actions it is to perform; the header therefore governs the layer""s operations.
The PDU created by the file transfer application in the application service layer is passed to the file transfer application residing at host B. If lost A and B are large mainframe computers, this application is likely an exact duplicate of the software at the transmitting host. The application might, however, perform a variety of functions, depending on the header it receives. It is conceivable that the data could be passed to another end-user application at host B, but in many instances the user at host A merely wants to obtain the services of a server protocol, such as a file transfer or email. If this is the case, it is not necessary for an end-user application process to be invoked at host B.
To return the retrieved data from the server at host B to the client at host A, the process is reversed. The data is transferred down through the layers in the host B machine, through the network, through the gateway, to the next network, and up the layers of host A to the end-user.
FIG. 3 is a block diagram of a network system 300 comprising a collection of computer networks connected to a plurality of nodes. The nodes are typically general purpose computers comprising a source node S, an end node N, a destination node D and a plurality of intermediate nodes or routers R1 and R2. Each node typically comprises a central processing unit (CPU) 302, a memory unit 304 and at least one network adapter 306 interconnected by a system bus 310. The memory unit 304 may comprise storage locations typically composed of random access memory (RAM) devices, which are addressable by the CPU 302 and network adapter 306. The memory unit typically provides temporary storage of information, such as, for example, executable processes and contents of data packets, as described further herein. An operating system, portions of which are typically resident in memory and executed by CPU, functionally organizes the node by, inter alia, invoking network operations in support of those processes executing in the CPU.
The computer networks included within system 300 may range from local area networks (LANs) to wide area networks (WANs). A LAN is a limited area network, while a WAN may be a public or private telecommunications facility that interconnects nodes widely dispersed using communication links. Communication among the nodes coupled to these networks is typically effected by exchanging discrete data xe2x80x9cpacketsxe2x80x9d specifying addresses of, e.g., source and destination nodes. Since the system shown in FIG. 3 comprises a relatively small group of interconnected LANs 1-3, it is typically maintained as an autonomous domain. The intermediate nodes, typically routers, are configured to facilitate the flow of data packets throughout the domain 300 by routing those packets to the proper receiving nodes.
In general, when a source node S transmits a packet over LAN 1, the packet is sent to all nodes on that LAN. If the intended recipient of the packet is connected to LAN 3, the packet is routed through router R1, over LAN 2 and through R2 onto LAN 3. A key function of a router is determining the next node to which the packet is sent; this routing function is typically performed by network layer 360 of a protocol stack 350 within each node. Typically, the packet includes two destination addresses: the address of the final destination node and the address of the next node along the route. The final destination address remains constant as the packet traverses the networks along an optimal route, while the next destination address changes as the packet moves from node to node along the optimal route through the networks.
Specifically, when source node S sends a packet to destination node D, i.e., the final destination address, the packet is transmitted onto LAN 1 with a next destination address specifying the address of router R1. Address information embedded in the packet, which is processed by the higher-layer software of the protocol stack 350, identifies the final destination of the packet as node D. Based on this information, R1 determines that the next node along the optimal path is router R2 and proceeds to pass the packet onto LAN 2 for reception by that node. Router R2 then determines that the next node is the final destination node D and transmits the packet over LAN 3 to node D.
Future Internet will support both high-priority multimedia traffic, such as, voice and video streams, and low-priority data traffic such as, best-effort traffic. Typically, Quality-of-Service (QoS) delivery of high-priority traffic requires stringent QoS guarantees. In order to meet these stringent QoS guarantees, various packet queuing algorithms have been developed, such as, for example, priority queuing and Weighted Fair Queuing (WFQ). These queuing algorithms are typically implemented at the router level, and more specifically at the QoS output queues where processed packets have been enqueued to await their turn to be forwarded or routed to the appropriate output interface line. A primary purpose of these queuing algorithms is to give preferential treatment to packets having higher priority (which are enqueued at the router output interface) over other enqueued packets having lower priority. However, the process of implementing these queuing algorithms in software can be quite challenging, as described in greater detail below.
The router CPU typically streamlines packet processing by processing one packet at a time. A new arriving packet may be immediately processed if the router CPU is idle. However, if the router CPU is not idle (e.g. when the router CPU is processing other packets) the arriving packet will sit in an input interface queue and await its turn for processing. It is difficult if not impossible for the router forwarding engine to take this waiting time into account in its queuing algorithm because the packet is not classified while waiting. The router does not know the source ID, destination ID, or traffic class of this packet before it is processed.
Thus, for example, when a burst of packets arrives at a router from different upstream nodes simultaneously, most of these packets will have to wait in their respective input interface queues before being processed. With increased number of interface cards, this waiting time can be significant. Moreover, deploying sophistocated queuing algorithms can significantly increase the processing time of a packet, which will also result in longer waiting time for packets sitting in the input interface queues.
With the possible increased waiting time and the fact that it is difficult to take this waiting time into consideration in the packet queuing algorithm, a delay-sensitive packet, such as, for example, a voice packet, may miss its xe2x80x9csupposedxe2x80x9d departing time even before it is processed. The xe2x80x9csupposedxe2x80x9d departing time is the time the packet should theoretically be transmitted to the down stream node according to the queuing algorithm, assuming that the packet can be processed immediately upon its arrival.
The above-described inaccuracies in the software implementation of packet forwarding and queuing algorithms can significantly increase the latency of delay-sensitive packets such as voice or video packets. Further, these inaccuracies reduce the possibility of end-to-end delay guarantees, and significantly affect the quality of voice or other audio applications over Internet.
It is desirable, therefore, to provide a technique which can significantly reduce packet latency associated with routing high priority or delay sensitive packets. It is also desirable to provide a technique which is simple in design, imposes little computational overhead, and which consumes only a limited amount of memory resources.
According to specific embodiments of the invention, a technique is provided for routing traffic in a packet-switched, integrated services network which supports a plurality of different service classes. More specifically, the technique of the present invention significantly reduces packet processing latency, particularly with respect to high priority or delay-sensitive packets. The technique of the present invention may be easily implemented in conventional routing systems. Further, it imposes little computational overhead, and consumes only a limited amount of memory resources within the system.
According to one aspect of the technique of the present invention, preferential treatment is given to those packets that are delay-sensitive at processing time by deferring full processing of non-delay-sensitive packets. Instead of processing every packet from decapsulation until it is placed into an appropriate output queue, the whole data path is broken into two phases. In Phase I, a newly arriving packet is pre-processed, which includes decapsulation and simple packet classification for identifying the priority of the packet and/or for determining whether the packet is delay-sensitive. If the packet is determined to be delay-sensitive, it is immediately and fully processed, which includes routing the packet to an appropriate output interface queue. However, if it is determined that the packet is not delay-sensitive, the packet is stored in an intermediate data structure to await full processing. After completing Phase I processing of at least some of the packets sitting in the input interface cards, Phase II processing begins. During Phase IT processing, at least a portion of the intermediate packets queued within the intermediate data structure are retrieved and fully processed.
According to a specific embodiment of the invention, a method is provided for routing traffic in a packet-switched, integrated services network which supports a plurality of different service classes. The network includes at least one router having at least one input interface and at least one output interface. The method includes preprocessing at least one packet queued at the input interface, wherein preprocessing includes classifying the packet to determine an associated priority level of the packet. Preprocessing does not include routing the packet to an appropriate output interface queue. If the associated priority level of the packet is at least priority P, the packet is fully processed, including routing the packet to an appropriate output interface queue. If, however, the associated priority level of the packet is less than priority P, the packet is stored in an intermediate data structure to await full processing.
A second specific embodiment of the present invention provides a method for routing traffic in a packet-switched, integrated services network which supports a plurality of different service classes. The network includes at least one router having at least one input interface and at least one output interface. The method comprises preprocessing at least one packet from the input interface to determine if the packet is delay-sensitive. The preprocessing includes classifying the packet to determine an associated priority level of the packet. If the packet is determined to be delay-sensitive, it is immediately and fully processed, which includes routing the packet to an appropriate output interface queue. If the packet is determined not to be delay-sensitive, the packet is stored in an intermediate data structure to await full processing. The intermediate data structure is used for queuing packets which have been preprocessed, but which have not yet been processed sufficiently to be routed to an appropriate output interface queue.
A third specific embodiment of the present invention provides a computer program product for routing traffic in a packet-switched integrated services network which supports a plurality of different service classes. The network includes at least one router. The router includes at least one input interface having at least one line input and at least one output interface. The computer program product comprises at least one computer useable medium having computer code embodied therein. The computer readable code comprises computer code for processing at least one packet from the input interface to determine if the packet is delay-sensitive, wherein the preprocessing code includes computer code for classifying the packet; computer code for fully processing the packet if the packet is determined to be delay-sensitive, the fully processing code including computer code for routing the packet to an appropriate output interface queue; and computer code for storing the packet in an intermediate data structure before fully processing the packet if the packet is determined not to be delay-sensitive. The intermediate data structure is used for queuing packets which have been preprocessed, but which have not yet been processed sufficiently to be routed to an output interface queue.
A fourth specific embodiment of the present invention provides a router for routing traffic in a packet-switched integrated services network which supports a plurality of different service classes. The router comprises a processor; at least one input interface; at least one output interface; and memory having at least one intermediate data structure. The processor is configured or designed to preprocess at least one packet from the input interface to determine if the packet is delay sensitive, wherein the preprocessing includes classifying the packet. The processor is further configured or designed to fully process the packet if the packet is determined to be delay sensitive, wherein fully processing includes routing the packet to an appropriate output interface queue. The processor is further configured or designed to store the packet in the intermediate data structure before fully processing the packet if the packet is determined not to be delay sensitive. The intermediate data structure is used for queuing packets which have been preprocessed, but which have not yet been processed sufficiently to be routed to an output interface queue.
A fifth specific embodiment of the present invention provides a router for routing traffic in a packet-switched integrated services network which supports a plurality of different service classes. The router comprises a processor; at least one input interface; at least one output interface including at least one output interface data structure for queuing packets which have been fully processed by the processor; and at least one intermediate data structure for queuing intermediate packets which have been preprocessed, but which have not yet been processed sufficiently to be routed to the output interface data structure.
Additional features and advantages of the present invention will become apparent from the following description of its preferred embodiments, which description should be taken in conjunction with the accompanying drawings.